// bfs 解决 FloodFill 算法
// 类似于二叉树的层序遍历，借助队列存放坐标
// 出队时上下左右四个方向扫描，将具有相同性质的坐标加入队列，循环直至队列为空即完成了 FloodFill 算法
// 经典题目 - 找连通块的数量，通过遍历的方式每找到一个符合要求的坐标，就使用 bfs 搜索全部的连通区域，并且标记
// 经典题目 - 找连通块的最大面积，通过遍历的方式找到一个符合要求的坐标， 利用 bfs 搜索全部连通的区域，并且标记，统计数量
// 经典题目 - 找被包围的区域，正难则反，找出不被包围的区域，剩下的区域就是被包围的区域

// 例题 4：
// 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获 所有 被围绕的区域：
//
//        连接：一个单元格与水平或垂直方向上相邻的单元格连接。
//        区域：连接所有 'O' 的单元格来形成一个区域。
//        围绕：如果您可以用 'X' 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 'X' 单元格围绕。
//        通过 原地 将输入矩阵中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。你不需要返回任何值。
//
//        示例 1：
//
//        输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
//
//        输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
//
//        解释：
//        在上图中，底部的区域没有被捕获，因为它在 board 的边缘并且不能被围绕。
//
//        示例 2：
//
//        输入：board = [["X"]]
//
//        输出：[["X"]]
//
//        提示：
//
//        m == board.length
//        n == board[i].length
//        1 <= m, n <= 200
//        board[i][j] 为 'X' 或 'O'

// 解题思路：
// 利用 bfs 找不被包围的区域，剩下的就是被包围的区域

import java.util.LinkedList;
import java.util.Queue;

public class Solve {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int m = 0; int n = 0;
    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;
        for(int j = 0; j < n; j++){
            if(board[0][j] == 'O') bfs(board, 0, j);
            if(board[m - 1][j] == 'O') bfs(board, m - 1, j);
        }
        for(int i = 0; i < m; i++){
            if(board[i][0] == 'O') bfs(board, i, 0);
            if(board[i][n - 1] == 'O') bfs(board, i, n - 1);
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == 'A') board[i][j] = 'O';
                else if(board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }
    public void bfs(char[][] board, int i, int j){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {i, j});
        board[i][j] = 'A';
        while(!queue.isEmpty()){
            int[] point = queue.poll();
            int a = point[0];
            int b = point[1];
            for(int k = 0; k < 4; k++){
                int x = a + dx[k];
                int y = b + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O'){
                    queue.offer(new int[] {x, y});
                    board[x][y] = 'A';
                }
            }
        }
    }
}
